namespace Test.ConsoleProgram.Algorithm.Interview
{
    [TestDescription("面试题 08.03. 魔术索引")]
    public class No00080003_FindMagicIndex : AbsBaseTestItem
    {
        /*
        魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。
        给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。
        若有多个魔术索引，返回索引值最小的一个。
        */
        public override void OnTest()
        {
            Assert.TestExe(FindMagicIndex, new int[] { 0, 2, 3, 4, 5 }, 0);
            Assert.TestExe(FindMagicIndex, new int[] { 1, 1, 1 }, 1);

            Assert.TestExe(FindMagicIndex_2, new int[] { 0, 2, 3, 4, 5 }, 0);
            Assert.TestExe(FindMagicIndex_2, new int[] { 1, 1, 1 }, 1);
        }

        /// <summary>
        /// 暴力解法
        /// </summary>
        public int FindMagicIndex(int[] nums)
        {
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] == i)
                {
                    return i;
                }
            }
            return -1;
        }

        /// <summary>
        /// 方法一：二分剪枝
        /// </summary>
        public int FindMagicIndex_2(int[] nums)
        {
            int getAnswer(int[] nums, int left, int right)
            {
                if (left > right)
                {
                    return -1;
                }

                int mid = (right - left) / 2 + left;
                int leftAnswer = getAnswer(nums, left, mid - 1);
                if (leftAnswer != -1)
                {
                    return leftAnswer;
                }
                else if (nums[mid] == mid)
                {
                    return mid;
                }
                return getAnswer(nums, mid + 1, right);
            }

            return getAnswer(nums, 0, nums.Length - 1);
        }
    }
}
